#include <stdio.h>
#include <stdlib.h>
#include "SeqList.h"
#include "Sort.h"

#define true 1
#define false 0

#define Init_ArrayPoint(name,log) SeqList* name = (SeqList*)malloc(sizeof(SeqList));\
                                   if(name == NULL)\
                                   {printf(log);return NULL;}\
                                   name->size = 0;
#define FreeArrayPoint(name) if(name != NULL) {free(name); name = NULL};

//初始化顺序表
int  SeqListInit(SeqList *ps)
{ 
    ps->arr = (ElementType*)malloc(sizeof(ElementType) * 10);
    if(ps->arr == NULL)
    {
        printf("SeqListInit error!\n");
        return false;
    }
    ps->size = 0;
    ps->capacity = 10;
    return true;
}

//打印顺序表
void SeqListPrint(SeqList *ps)
{
    for(int i = 0; i < ps->size; ++i)
    {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

// 清除顺序表
void SeqListClear(SeqList *ps)
{
    free(ps->arr);
    ps->size = 0;
}

//扩容
int ExtendCapacity(SeqList *ps)
{
    ElementType *temp = ps->arr;
    ps->arr = (ElementType *)malloc(sizeof(ElementType) * ps->capacity*2);
    if(ps->arr == NULL)
    {
        printf("ExtendCapacity error!\n");
        return false;
    }
    for (int i = 0; i < ps->size; i++)
    {
        ps->arr[i] = temp[i];
    }
    ps->capacity *= 2;
    free(temp);
    return true;
}


//尾插
int  SeqListPushBack(SeqList *ps, ElementType element)
{
    if(ps->size == ps->capacity)
    {
       if(ExtendCapacity(ps) == false)
       {
           printf("can not contain more elements!\n ");
           return false;
       }
    }
    ps->arr[ps->size] = element;
    ps->size++;
    return true;
}


//头插
int SeqListPushFront(SeqList *ps, ElementType element)
{
    return SeqListInsert(ps, 0, element);
}

//尾删
int SeqListPopBack(SeqList *ps)
{
    if(ps->size <= 0)
    {
        return false;
    }
    ps->size--;
    return true;
}

//头删
int SeqListPopFront(SeqList *ps)
{
    int i = SeqListEraseByIndex(ps, 0);
}

//任意位置插入一个元素
int SeqListInsert(SeqList *ps, int index, ElementType element)
{
    if(ps->size == ps->capacity)
    {
       if(ExtendCapacity(ps) == false)
       {
           printf("can not contain more elements!\n ");
           return false;
       }
    }
    if(index < 0 || index > ps->size )
    {
        printf("insertindex invalid place!\n");
        return false;
    }
    for(int i = ps->size - 1; i >= index; --i)
    {
        ps->arr[i+1] = ps->arr[i];
    }
    ps->arr[index] = element;
    ps->size++;
    return true;
}

//任意位置删除一个元素
int SeqListEraseByIndex(SeqList *ps, int index)
{
    if(index < 0 || index > ps->size)
    {
        printf("removeindex invalid place!\n");
        return false; 
    }
    for(int i = index; i < ps->size - 1; ++i)
    {
        ps->arr[i] = ps->arr[i+1];
    }
    ps->size--;
    return true;
}

//删除指定元素
void SeqListEraseByElement(SeqList *ps, ElementType element)
{
    for(int i = 0; i < ps->size; i++)
    {
        if(ps->arr[i] == element)
        {
            SeqListEraseByIndex(ps,i);
            i--;
        }
    }
}

//查找下标所对应的值
ElementType* SeqListFindByIndex(SeqList *ps, int index )
{
        if(index < 0 || index >= ps->size)
    {
        printf("Findindex invalid place!\n");
        return NULL;
    }
    return &ps->arr[index];
}

//查找指定元素下标位置，并统计元素个，个数放在返回结构的首地址
ElementType*  SeqListFindByElement(SeqList *ps, ElementType element)
{
   ElementType* findVector = (ElementType*) malloc(sizeof(ElementType) * (ps->size +1));
   if(findVector == NULL)
   {
    printf(" malloc error!\n");
    return NULL;
   }

   int count = 0;
   for(int i = 0; i < ps->size; i++)
   {
      if(ps->arr[i] == element)
      {
        count++;
        findVector[count] = i;
      }
   }
   findVector[0] = count;
   return findVector;
}

//查找指定元素下标位置，不统计个数（字符数组实现）
ElementType* SeqListFindByElement2(SeqList *ps, ElementType element)
{
   ElementType* findVector = (ElementType*) malloc(sizeof(ElementType) * (ps->size +1));
   if(findVector == NULL)
   {
    printf(" malloc error!\n");
    return NULL;
   }

   int count = 0;
   for(int i = 0; i < ps->size; i++)
   {
      if(ps->arr[i] == element)
      {
        findVector[count] = i;
        count++;
      }
   }
   findVector[count] = -1;
   return findVector;
}

//通过下标设定值
void SeqListSetValueByIndex(SeqList *ps, int index, ElementType element)
{
    if(index < 0 || index > ps->size)
    {
        printf("SetValueByIndex invalid place!\n");
        return ;
    }
    ps->arr[index] = element;
}

//更改元素值
void SeqListSetValueByElement(SeqList *ps, ElementType oldValue, ElementType newValue)
{
    for (int i = 0; i < ps->size; i++)
    {
        if(ps->arr[i] == oldValue)
            ps->arr[i] = newValue;
    }
}

//求交集
SeqList* SeqListFindIntersection(SeqList *array1,SeqList *array2)
{
    SeqList *intersection = (SeqList*)malloc(sizeof(SeqList));
    if(intersection == NULL)
    {
        printf("FindIntersection malloc error!\n");
        return NULL;
    }
    SeqListInit(intersection);
    for(int i = 0; i < array1->size; i++)
    {
        for(int j = 0; j < array2->size; j++)
        {
            if(array1->arr[i] == array2->arr[j])
            {   
                int flag = 0;
                for(int k = 0; k < intersection->size; k++)
                {
                    if(intersection->arr[k] == array1->arr[i])
                    {
                        flag = 1;
                    }
                }
                if(flag == 0)
                   SeqListPushBack(intersection,array1->arr[i]);
            }
        }
    }
    return intersection;
}

//去重
void Duplication(SeqList *ps)
{
    QuickSort_Pointer(ps->arr, 0, ps->size - 1);
    for(int i = 1; i < ps->size; i++)
    {
        if(ps->arr[i] == ps->arr[i-1])
        {
            SeqListEraseByIndex(ps,i);
            i--;
        }
    }
}

//求并集
SeqList* SeqListFindUnionSet(SeqList *array1,SeqList *array2)
{
    SeqList* UnionSet = (SeqList*)malloc(sizeof(SeqList));
    if (UnionSet == NULL)
    {
        printf("FindUnionSet malloc error!\n");
        return NULL;
    }
    SeqListInit(UnionSet);
    for(int i = 0; i < array1->size; i++)
    {
        SeqListPushBack(UnionSet,array1->arr[i]);
    }
    for(int i = 0; i < array2->size; i++)
    {
        SeqListPushBack(UnionSet,array2->arr[i]);
    }

    Duplication(UnionSet);
    return UnionSet;
}

//求并集（归并思想,不去重）
SeqList* SeqListMergeArray(SeqList *array1, SeqList *array2)
{
    QuickSort_Pointer(array1->arr, 0, array1->size - 1);
    QuickSort_Pointer(array2->arr, 0, array2->size - 1);

    Init_ArrayPoint(merge,"MergeArray malloc error!\n");
    SeqListInit(merge);
    int i = 0, j = 0;
    while(i < array1->size && j < array2->size )
    {
        if(array1->arr[i] < array2->arr[j])
        {
            SeqListPushBack(merge, array1->arr[i]);
            i++;
        }
        else 
        {
            SeqListPushBack(merge, array2->arr[j]);
            j++;
        }
    }
    while(i < array1->size)
    {
        SeqListPushBack(merge, array1->arr[i]);
        i++;
    }
        while(j < array2->size)
    {
        SeqListPushBack(merge, array2->arr[j]);
        j++;
    }

    return merge;
}

